(function (global, document, undefined) {
    function Edge(source, target, data, virtual) {
        this.source = source;
        this.target = target;
        this.data = data || {};
        this._virtual = virtual || false;
    }

    function Vertex(index, data) {
        this.index = index;
        this.data = data || {};
        this.edges = [];
        this.reverseEdges = [];
    }

    Vertex.prototype = {
        constructor: Vertex,
        addEdge: function (target, data) {
            var edge = new Edge(this.index, target, data);
            this.edges.push(edge);
            return edge;
        },
        addReverseEdge: function (edge) {
            this.reverseEdges.push(edge);
        },
        removeEdge: function (target) {
            var index = -1;
            this.eachEdge(function (edge, i) {
                if (edge.target === target) {
                    index = i;
                }
            });
            if (index > 0) {
                this.edges.splice(index, 1);
            }
        },
        eachEdge: function (callback) {
            var edges = this.edges;
            var reverseEdges = this.reverseEdges;
            for (var i = 0, length = edges.length; i < length; i++) {
                callback(edges[i], i);
            }
            for (var j = 0, reverselength = reverseEdges.length; j < reverselength; j++) {
                callback(reverseEdges[j], j);
            }
        }
    };
    function Graph(vertices, edges, edgeRefType) {
        this._vertices = vertices;
        this._edges = edges;
        this.vertices = {};
        this.edgeMap = {};
        this.edgeRefType = edgeRefType || "index";
        for (var i = 0, vlength = vertices.length; i < vlength; i++) {
            var key = (edgeRefType == null || edgeRefType == "index") ? i : vertices[i][edgeRefType];
            //var key = (this.edgeRefType == "index") ? i : vertices[i][this.edgeRefType ];
            this.addVertex(key, vertices[i]);
        }
        for (var j = 0, elength = edges.length; j < elength; j++) {
            var edge = edges[j];
            this.addDirectedEdge(edge.source, edge.target, edge);
        }
        for (j = 0; j < elength; j++) {
            var edge = edges[j];
            this.addReverseEdge(edge.source, edge.target, edge);
        }
    }

    Graph.prototype = {
        constructor: Graph,
        getVertex: function (value) {
            // target compitable with array index
            if (value.index != null) {
                return this.vertices[value.index];
            } else {
                return this.vertices[value];
            }
        },
        addVertex: function (key, data) {
            var vertices = this.vertices;
            vertices[key] = new Vertex(key, data);
        },
        getEdge: function (source, target) {
            return this.edgeMap[source + '-' + target];
        },
        addDirectedEdge: function (source, target, data) {
            var sourceVertex = this.getVertex(source);
            var targetVertex = this.getVertex(target);
            if (sourceVertex && targetVertex) {
                this.edgeMap[sourceVertex.index + '-' + targetVertex.index] = sourceVertex.addEdge(targetVertex.index, data);
            }
        },
        addReverseEdge: function (source, target, data) {
            var sourceVertex = this.getVertex(source);
            var targetVertex = this.getVertex(target);
            if (sourceVertex && targetVertex) {
                if (!this.edgeMap[targetVertex.index + '-' + sourceVertex.index]) {
                    targetVertex.addReverseEdge(this.edgeMap[sourceVertex.index + '-' + targetVertex.index]);
                }
            }
        },
        addEdge: function (source, target, data) {
            this.addDirectedEdge(source, target, data);
            this.addReverseEdge(target, source, data);
        },
        removeDirectedEdge: function (source, target) {
            this.getVertex(source).removeEdge(target);
            this.edgeMap[source + '-' + target] = null;
        },
        removeEdge: function (source, target) {
            this.removeDirectedEdge(source, target);
            this.removeDirectedEdge(target, source);
        },
        hasEdge: function (source, target, directed) {
            var edgeMap = this.edgeMap;
            if (directed) {
                return edgeMap[source + '-' + target] || false;
            }
            else {
                return edgeMap[source + '-' + target] || edgeMap[target + '-' + source] || false;
            }
        },
        eachVertex: function (callback) {
            fruit.util.each(this.vertices, function (vertex, key) {
                if (vertex && vertex.data) {
                    callback(vertex, key);
                }
            });
        },
        eachEdge: function (callback) {
            var edgeMap = this.edgeMap,
                key, edge;
            for (key in edgeMap) {
                edge = edgeMap[key];
                if (edge) {
                    callback(edge);
                }
            }
        },
        eachConnectedVertices: function (vertex) {
            var self = this;
            var vertices = [];
            vertex.eachEdge(function (edge) {
                vertices.push(self.getVertex(edge.target));
            });
            return vertices;
        },
        indexing: function () {
        },
        filter: function (condition) {
//        var self = this;
//        this.eachEdge(function (edge) {
//            if (edge.virtual) {
//                self.removeDirectedEdge(edge.source, edge.target);
//            }
//        });
//        this.eachVertex(function (vertex, index) {
//            if (!condition(vertex, index)) {
//                vertex.data.hidden = true;
//                var vertices = self.eachConnectedVertices(vertex);
//                //targetdo update by each
//                for (var i = 0, length = vertices.length; i < length; i++) {
//                    for (var j = i + 1; j < length; j++) {
//                        var source = vertices[i].index;
//                        var target = vertices[j].index;
//                        if (!self.hasEdge(source, target)) {
//                            self.addDirectedEdge(source, target).virtual = true;
//                        }
//                        if (!self.hasEdge(target, source)) {
//                            self.addDirectedEdge(target, source).virtual = true;
//                        }
//                    }
//                }
//            } else {
//                vertex.data.hidden = false;
//            }
//        });
        },
        getVertices: function (visible) {
            var vertices = [];
            this.eachVertex(function (vertex) {
                vertices.push(vertex.data);
            });
            return vertices;
        },
        getEdges: function (visible) {
            var edges = [];
            var self = this;
            var tempVertices = this.getVertices();
            var util = fruit.util;
            this.eachEdge(function (edge) {
                var sourceVertex = self.getVertex(edge.source);
                var targetVertex = self.getVertex(edge.target);
                edges.push({
                    source: util.indexOf(tempVertices, sourceVertex.data),
                    target: util.indexOf(tempVertices, targetVertex.data)
                });
            });
            return edges;
        },
        getBound: function () {
            var min_x = 10000;
            var max_x = 0;
            var min_y = 10000;
            var max_y = 0;
            fruit.util.each(this.vertices, function (vertex, key) {
                if (vertex && vertex.data) {
                    var data = vertex.data;
                    min_x = Math.min(min_x, data.x);
                    max_x = Math.max(max_x, data.x);
                    min_y = Math.min(min_y, data.y);
                    max_y = Math.max(max_y, data.y);
                }
            });
            return {
                x: min_x,
                y: min_y,
                width: max_x - min_x,
                height: max_y - min_y
            };
//        var vertices = [].slice.call(this.vertices);
//        vertices.sort(function (a, b) {
//            return a.data.x - b.data.x;
//        })
//        bound.x = vertices[0].data.x;
//        bound.width = vertices[vertices.length - 1].data.x - bound.x;
//        vertices.sort(function (a, b) {
//            return a.data.y - b.data.y;
//        })
//        bound.y = vertices[0].data.y;
//        bound.height = vertices[vertices.length - 1].data.y - bound.y;
            // return bound;
        },
        getXX: function (condition) {
            var vertices = [];
            var verticesMap = {};
            var edges = [];
            var _edges = this.getEdges();
            var self = this;
            var isDefined = fruit.util.isDefine;
            this.filter(condition);
            this.eachVertex(function (vertex, i) {
                if (vertex.data.hidden == false) {
                    verticesMap[i] = vertices.length;
                    vertices.push(vertex.data);
                }
            });
            this.eachEdge(function (edge) {
                if (edge.source in verticesMap && edge.target in verticesMap) {
                    edges.push({
                        source: verticesMap[edge.source],
                        target: verticesMap[edge.target],
                        virtual: edge.virtual
                    })
                }
            });
            return {
                vertices: vertices,
                edges: edges
            }
        }

    };


    fruit.Graph = Graph;
}(window, document, undefined));